public class HashBuck {

    //定义内部类 链表节点
    static class Node{
        public int key;
        public int val;
        public Node next;
        public Node(int key,int val){
            this.key=key;
            this.val=val;
        }
    }

    //定义链表头节点组成的引用数组以及已使用大小
    public Node[] array;
    public int usedSize;

    //定义期望的负载因子
    public double loadFactor=0.75;

    public HashBuck(){
        array=new Node[10];
    }

    //HashBuck的插入方法
    public void put(int key,int val){

        //定义哈希函数
        int index=key% array.length;
        Node cur=array[index];

        //遍历当前链表判断是否存在插入值
        while (cur!=null){
            if(cur!=null){
                if(cur.key==key){
                    cur.val=val;
                    return;
                }
                cur=cur.next;
            }
        }

        //运行到这里说明没有插入值，此时对链表执行插入操作（这里使用头插）
        Node node=new Node(key,val);
        node.next=array[index];
        array[index]=node;
        usedSize++;

        //通过负载因子判断是否需要进行扩容
        if(loadFactorCount()>=loadFactor){

            //需要进行扩容，调用扩容方法
            resize();
        }
    }

    //计算负载因子的私有方法（供插入方法使用）
    private double loadFactorCount(){
        return usedSize*1.0/ array.length;
    }

    //对HashBuck进行扩容的私有方法（供插入方法使用）
    private void resize(){

        //定义一个扩容后的新的引用数组
        Node[] newArray=new Node[array.length*2];

        //遍历引用数组
        for (int i=0;i< array.length;i++){
            Node cur=array[i];

            //遍历链表
            while(cur!=null){

                //扩容后必须使用新的数据结构所对应的哈希函数，保证新的数据结构与key值之间的哈希映射关系
                int newIndex=cur.key% newArray.length;
                Node curN=cur.next;
                cur.next=newArray[newIndex];
                newArray[newIndex]=cur;
                cur=curN;
            }
        }

        //将新的引用赋值给原引用
        array=newArray;
    }

    //HashBuck的获取方法
    public int get(int key){

        //利用哈希函数寻找key值
        int index=key% array.length;
        Node cur=array[index];

        //遍历当前链表寻找输入的key值
        while (cur!=null){
            if(cur!=null){
                if(cur.key==key){
                    return cur.val;
                }
                cur=cur.next;
            }
        }

        //运行到这里说明不存在输入的key值，返回默认值-1
        return -1;
    }
}
